package 动态规划.可dp可二分;

public class 数组分成k组 {

	
	public static int solution(int nums[],int k) {
		int len = nums.length;
		return recursion(0,k,len);
	}
	
	public static int recursion(int index,int k,int len) {
		if(index == len)
			return k == 0 ? 1 : 0;
		
		int ans = 0;
		for(int scale = 1;index + scale <= len;scale ++) {
			
			ans += recursion(index + scale,k - 1,len);
		}
		return ans;
	}
	
	public static void main(String []args) {
		int nums[] = {1,2,3,4,5,1,1,1};
		int k = 3;
		System.out.println(solution(nums,k));
//		int nums [] = {7,2,5,10,8};
////		int nums [] = {1,2,3,4,5};
//		int k = 2;
//		System.out.println(minMaxSolution(nums,k));
	}
	
	
	/**
	 * 调用函数
	 */
	public static int minMaxSolution(int nums[],int k) {
		int len = nums.length;
		int [] preSum = new int [len + 1];
		for(int i = 0;i < len;i++) {
			preSum[i + 1] = preSum[i] + nums[i];
		}
		return minMax(0,k,len,preSum);
	}
	
	/**
	 * 分成 k 组之后， 求  min {  max{ans1{.......}}, max{ans2{......}} ,.......}
	 * 求 min { max { ...... } }
	 * 这写的 不对!
	 */
	public static int minMax(int index,int k,int len,int [] preSum) {
		if(index == len)
			return k == 0 ? 0 : Integer.MAX_VALUE;
		if(k == 0)
			return Integer.MAX_VALUE;
//		int temp = 0;
		int ans = Integer.MAX_VALUE;
		for(int scale = 1;index + scale  <= len;scale++) {
//			temp = preSum[index + scale] - preSum[index];
//			temp = Math.max(preSum[index + scale] - preSum[index], minMax(index + scale,k - 1,len,preSum));
			ans = Math.min(ans, Math.max(preSum[index + scale] - preSum[index], minMax(index + scale,k - 1,len,preSum)));
		}
		return ans;
	}
	
}
